import random
import igraph
import os

class NodeGraph (igraph.Graph):

	def add_vertex(self, name=None, **kwds):
		if not ("node" in kwds): kwds["node"] = 1
		else : kwds["node"] = int(bool(kwds["node"]))
		super(NodeGraph, self).add_vertex(name, **kwds)

	def add_vertices(self, vertices):
		start = len(self.vs)
		super(NodeGraph, self).add_vertices(vertices)
		for index in range(start, len(self.vs)): self.vs[index]["node"] = True

# compute a fat tree topology from an integer parameter n

def compute_fat_tree_topology (n):

# init the graph and its set of vertices

	g = igraph.Graph(directed=True)
	g.add_vertices(range(5*(n)**2))

# add edges to the graph

	for k in range(2*n):
		for i in range(n):
			for j in range(n):
				g.add_edge(n**2+n*k+i, (n*j+i)%(n**2))
				g.add_edge((n*j+i)%(n**2), n**2+n*k+i)
				g.add_edge(n**2+n*k+i, 3*n**2+n*k+j)
				g.add_edge(3*n**2+n*k+j, n**2+n*k+i)
	return g

def compute_tacas_tree_topology(n):

# generate the graph and its set of vertices

	g = igraph.Graph(directed = True)
	g.add_vertices(list(range(n*(n+1))))
	g.vs["cor"] = [int(i<n) for i in range(len(g.vs))]

# add edges per unit and cor nodes

	for n1 in range(n) :
		for n2 in range(n) :
			g.add_edge(n1, n*(n2+1)+n1)
			g.add_edge(n*(n2+1)+n1, n1)
			g.add_edge(n*(n1+1)+n2, n*(n1+1)+(n2+1)%n)
			g.add_edge(n*(n1+1)+(n2+1)%n, n*(n1+1)+n2)
	return g

# compute a b-cube topology from an integer parameter n

def compute_bcube_topology(n):

# generate the graph and its set of vertices

	g = igraph.Graph(directed = True)
	g.add_vertices(list(range(n*(n+2))))
	g.vs["cor"] = [int(i<n) for i in range(len(g.vs))]

# add edges per pyramids and cor nodes

	for n1 in range(n) :
		for n2 in range(n) :
			g.add_edge(n1, n*(n2+2)+n1)
			g.add_edge(n*(n2+2)+n1, n1)
			g.add_edge(n+n2, n*(n2+2)+n1)
			g.add_edge(n*(n2+2)+n1, n+n2)
	return g

# load a topology from a provided file

def read_topology (filename) :
	if os.path.splitext(filename)[1]==".gml" : 
		return igraph.Graph.Read_GML(filename).as_directed()
	elif os.path.splitext(filename)[1]==".graphml" : 
		return igraph.Graph.Read_GraphML(filename).as_directed()
	else : 
		raise ValueError ("Unknown file extension: "+filename)


# simplify a graph if it is possible

def simplify_topology (g) :

# if a vertex has exactly two neighbours replace its edges by a direct one between its neighbours

	for v in range(len(g.vs)):
		neighbours = set(g.neighbors(v))
		if (len(neighbours))==2:

# remove the path in the first direction if it exists

			u, w = neighbours
			if not g.are_connected (u, w):
				e1 = g.get_eid(u, v, error=False)
				e2 = g.get_eid(v, w, error=False)

				if e1!=-1 and e2!=-1:
					capacity = min(g.es[e1]["capacity"], g.es[e2]["capacity"])
					weight = g.es[e1]["weight"] + g.es[e2]["weight"]
					g.delete_edges(e1, e2)
					edge = g.add_edge(u, w)
					edge["capacity"] = capacity
					edge["weight"] = weight

# remove the path in the second direction if it exists

			if not g.are_connected(w, u):
				e1 = g.get_eid(v, u, error=False)
				e2 = g.get_eid(w, v, error=False)

				if e1!=-1 and e2!=-1:
					edge = g.add_edge(w, u)
					edge["capacity"] = min(g.es[e1]["capacity"], g.es[e2]["capacity"])
					edge["weight"] = g.es[e1]["weight"] + g.es[e2]["weight"]
					g.delete_edges(e1, e2)

	return g

# compute a pseudo random permutation of size k

def pseudo_random_permutations (k):
	perm = list(range(k))
	res = list()

	while perm:
		idx = int(random.uniform(0, len(perm)))
		val = perm.pop(idx)
		res.append(val)

	return res